package com.gxc.array;

/**
 * 给你一个二维数组matrix，其中每个数都是正数，要求从左上角走到右下角。
 * 每一步只能向右或者向下，沿途经过的数字要累加起来。最后请返回最小的路径和。
 *
 * 解法：
 * dp
 * 每一步只能向右或者向下，可得每一个位置的值由上方或左方决定，第一行第一列初始化后，推导[行-1][列-1]的最小值
 */
public class MinimumPathLength {

    public static void main(String[] args) {
        int[][] matrix = random();
        //println(matrix);

        int size = (int) (Math.random() * 1000);
        for (int i = 0; i < size; i++) {
            int[][] randommatrix = random();
            if (minLength(randommatrix) != minLength2(randommatrix) ||
                    minLength(randommatrix)!=recursion(randommatrix) ||
                    recursion(randommatrix)!=minLength3(randommatrix) ||
                    minLength3(randommatrix)!=minLength4(randommatrix)) {
                println(randommatrix);
                System.out.println("算法有问题");
                break;
            }
        }

        System.out.println(minLength(matrix));
        System.out.println(minLength2(matrix));
    }

    /**
     * 不使用空间优化DP
     * @param matrix
     * @return
     */
    public static int minLength(int[][] matrix) {
        if (matrix == null || matrix.length ==0 || matrix[0].length==0) return 0;

        int[][] dp = new int[matrix.length][matrix[0].length];
        //初始化第一行
        for (int col = 0; col < matrix[0].length; col++) {
            dp[0][col] = col > 0 ? (dp[0][col-1] + matrix[0][col]):matrix[0][col];
        }
        //初始化第一列
        for (int row = 0; row < matrix.length; row++) {
            dp[row][0] = row > 0 ?(dp[row-1][0] + matrix[row][0] ): matrix[row][0];
        }
        for (int row = 1; row < matrix.length; row++) {
            for (int col = 1; col < matrix[row].length; col++) {
                dp[row][col] = Math.min(dp[row-1][col], dp[row][col-1]) + matrix[row][col];
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }

    /**
     * 使用空间优化dp
     * 由于每一个位置的值由上方或左方决定，原来的二维数组可以压缩成一维数组（单行dp）
     * @param matrix
     * @return
     */
    public static int minLength2(int[][] matrix) {
        if (matrix == null || matrix.length ==0 || matrix[0].length==0) return 0;

        int[] dp = new int[matrix[0].length];
        //初始化第一行
        for (int col = 0; col < matrix[0].length; col++) {
            dp[col] = col > 0 ? (dp[col-1] + matrix[0][col]):matrix[0][col];
        }
        for (int row = 1; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) {
                if (col == 0) {
                    dp[col] = dp[col] + matrix[row][col];
                } else {
                    dp[col] = Math.min(dp[col], dp[col-1]) + matrix[row][col];
                }
            }
        }
        return dp[dp.length-1];
    }

    //递归
    public static int recursion(int[][] matrix) {
        if (matrix == null || matrix.length ==0 || matrix[0].length==0) return 0;

        return process(matrix, 0, 0);
    }

    private static int process(int[][] matrix, int row, int col) {
        //到达最后一个位置
        if (row == matrix.length-1 && col == matrix[0].length-1) {
            return matrix[row][col];
        }

        int min = 0;
        if (row<matrix.length-1 && col<matrix[0].length-1) {
            min = Math.min(process(matrix, row, col+1), process(matrix, row+1, col));
        } else if (row == matrix.length-1){
            min = process(matrix, row, col+1);
        } else {
            min = process(matrix, row+1, col);
        }
        return matrix[row][col] + min;
    }

    //递归推导dp
    public static int minLength3(int[][] matrix) {
        if (matrix == null || matrix.length ==0 || matrix[0].length==0) return 0;
        int[][] dp = new int[matrix.length][matrix[0].length];

        dp[matrix.length-1][matrix[0].length-1] = matrix[matrix.length-1][matrix[0].length-1];
        for (int col = dp[0].length-2; col >= 0; col--) {
            dp[matrix.length-1][col] = dp[matrix.length-1][col+1] + matrix[matrix.length-1][col];
        }
        for (int row = dp.length-2; row >= 0; row--) {
            dp[row][matrix[0].length-1] = dp[row+1][matrix[0].length-1] + matrix[row][matrix[0].length-1];
        }
        for (int row = matrix.length-2; row >= 0; row--) {
            for (int col = matrix[row].length-2; col >= 0; col--) {
                dp[row][col] = Math.min(dp[row][col+1], dp[row+1][col]) + matrix[row][col];
            }
        }
        return dp[0][0];
    }

    //递归推导dp，空间优化
    public static int minLength4(int[][] matrix) {
        if (matrix == null || matrix.length ==0 || matrix[0].length==0) return 0;
        int[] dp = new int[matrix[0].length];

        dp[dp.length-1] = matrix[matrix.length-1][matrix[0].length-1];
        for (int col = dp.length-2; col >= 0; col--) {
            dp[col] = dp[col+1] + matrix[matrix.length-1][col];
        }
        for (int row = matrix.length-2; row >= 0; row--) {
            for (int col = matrix[row].length-1; col >= 0; col--) {
                if (col == matrix[0].length-1) {
                    dp[col] = dp[col] + matrix[row][col];
                } else {
                    dp[col] = Math.min(dp[col+1], dp[col]) + matrix[row][col];
                }
            }
        }
        return dp[0];
    }

    private static int[][] random() {
        int rowR = (int) (Math.random()*10)+1;
        int colR = (int) (Math.random()*10)+1;
        int[][] matrix = new int[rowR][colR];
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) {
                matrix[row][col] = (int) (Math.random()*10+1);
            }
        }
        return matrix;
    }

    private static void println(int[][] matrix) {
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) {
                System.out.print(matrix[row][col] + " ");
            }
            System.out.println("");
        }
    }

}
